package arrAndstr;

import java.util.*;

/*
    207. 课程表
    拓扑图：
        我们代码实现逆推的时候，从多节点到前推
        0
            3
        1       5
            4
        2
    以上：
        刚开始0、1、2的入度为0，可以直接访问
        访问后3、4入度为0，继续访问
        最后5的入度也为0，继续访问

    优化：
        用BSF优化
        while (!bfs.isEmpty()){
            int course = bfs.poll();
            List<Integer> indexes = indexMap.getOrDefault(course, new ArrayList<>());
            numCourses--;
            for(int i = 0; i < indexes.size(); i++){
                // in[indexes[i]]--;
                if(--in[indexes.get(i)] == 0){
                   bfs.offer(indexes.get(i));
                }
            }

        }
        return  numCourses == 0;
 */
public class T207 {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Integer> map = new HashMap<>();  // 为每个节点对应的入度

        Map<Integer, List<Integer>> nodePreNodes = new HashMap<>();    // 每个节点的前置节点
//nodePreNodes.computeIfAbsent()
        // 设置每个节点的前直接点、设置每个节点的入度
        for (int[] prerequisite : prerequisites) {
            int postNode = prerequisite[0];
            int preNode = prerequisite[1];

            if (!nodePreNodes.containsKey(preNode)) {
                List<Integer> tempList = new ArrayList<>();
                tempList.add(postNode);
                nodePreNodes.put(preNode, tempList);
            } else {
                List<Integer> tempList = nodePreNodes.get(preNode);
                tempList.add(postNode);
                nodePreNodes.put(preNode, tempList);
            }

            if (!map.containsKey(postNode)) map.put(postNode, 1);
            else map.put(postNode, map.get(postNode) + 1);
        }

        // 获取入度为0的节点：
        Set<Integer> enter0Node = getEnter0(map, nodePreNodes);

        while (enter0Node.size() > 0) {
            for (Integer node : enter0Node) {
                // 0度节点关联的节点
                List<Integer> list = nodePreNodes.get(node);
                for (Integer i : list) {
                    map.put(i, map.get(i)-1);
                }
                nodePreNodes.remove(node);
            }

            removeEnter0(map);

            enter0Node = getEnter0(map, nodePreNodes);
        }

        return nodePreNodes.size()==0;
    }

    private static void removeEnter0(Map<Integer, Integer> map) {
        Set<Integer> set = new HashSet<>();

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue()==0)    set.add(entry.getKey());
        }

        for (Integer i : set) {
            map.remove(i);
        }
    }

    // map中为入度不为0的 --> 返回在后面map但不在前面map的节点
    private static Set<Integer> getEnter0(Map<Integer, Integer> map, Map<Integer, List<Integer>> nodePreNodes) {
        Set<Integer> set = new HashSet<>();

        for(Map.Entry<Integer, List<Integer>> entry : nodePreNodes.entrySet()) {
            if (!map.containsKey(entry.getKey()))   set.add(entry.getKey());
        }

        return set;
    }

    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = new int[][] {
            {1,0},
            {0,1},
//            {4,1},
//            {4,2},
//            {5,3},
//            {5,4}
        };

        System.out.println(canFinish(numCourses, prerequisites));
    }
}
